/**
 * 归并排序(分治)
 * 组递归地划分为两个子数组，然后分别对这两个子数组进行递归的归并排序，最后将两个有序子数组合并成一个有序数组。
 * mergeSort 函数用于递归地将数组划分为子数组，直到每个子数组只包含一个元素或为空。
 * 然后，merge 函数用于将两个有序子数组合并成一个有序数组。
 * 在 merge 函数中，分别设置左子数组和右子数组的索引，然后依次比较两个子数组的元素，将较小的元素添加到 result 数组中，
 * 直到其中一个子数组的元素全部添加完毕。然后将剩余子数组的元素依次添加到 result 数组中，最终得到有序的合并数组。
 */

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const len = arr.length;
  const middle = Math.floor(len / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  console.log("🚀 ~ merge ~ left, right:", left, right)
  const result = [];
  let lIndex = 0;
  let rIndex = 0;
  while (lIndex < left.length && rIndex < right.length) {
    if (left[lIndex] < right[rIndex]) {
      result.push(left[lIndex]);
      lIndex++;
    } else {
      result.push(right[rIndex]);
      rIndex++;
    }
  }
  return result.concat(left.slice(lIndex)).concat(right.slice(rIndex));
}
const arr = [9, 3, 10, 6, 2, 1, 5, 7, 8, 4];

const arr2 = mergeSort(arr);
console.log(arr2, "🍉");